830. Простые числа

Выведите все простые числа на отрезке от m до n включительно.

Вход. Два натуральных числа m и n (2 ≤ m ≤ n ≤ 300000).

Выход. Выведите все простые числа на отрезке [m; n] в порядке возрастания, по одному в строке. Если между m и n включительно нет простых чисел, выведите “Absent”.

Пример входа 1	Пример выхода 1
2 5	2 3 5
Пример входа 2	Пример выхода 2
4 4	Absent

РЕШЕНИЕ

простые числа

Анализ алгоритма

Переберем все натуральные числа на отрезке от m до n и выведем только простые. Если на отрезке [m; n] не оказалось ни одного простого числа, выведем сообщение “Absent”.

Реализация алгоритма

Функция IsPrime проверяет, является ли число n простым.

· Если n простое, функция возвращает 1.

· В противном случае функция возвращает 0.

int IsPrime(int n)

{

for(int i = 2; i <= sqrt(n); i++)

if (n % i == 0) return 0;

return 1;

}

Основная часть программы. Читаем входные данные.

scanf("%d %d",&m,&n);

Изначально предположим, что простые числа на отрезке отсутствуют. Установим flag = 0.

flag = 0;

Перебираем числа от m до n. Если текущее число является простым, выводим его и устанавливаем flag = 1.

for(i = m; i <= n; i++)

{

if (IsPrime(i))

{

printf("%d\n",i);

flag = 1;

}

}

Если не было выведено ни одного простого числа (flag = 0), выводим сообщение “Absent”.

if (flag == 0) puts("Absent");

Python реализация

import math

Функция IsPrime проверяет, является ли число n простым.

· Если n простое, функция возвращает 1.

· В противном случае функция возвращает 0.

def IsPrime(n):

for i in range(2, int(math.sqrt(n)) + 1):

if n % i == 0: return False

return True

Основная часть программы. Читаем входные данные.

m, n = map(int,input().split())

Изначально предположим, что простые числа на отрезке отсутствуют. Установим flag = 0.

flag = 0

Перебираем числа от m до n. Если текущее число является простым, выводим его и устанавливаем flag = 1.

for i in range(m, n + 1):

if IsPrime(i):

print(i)

flag = 1

Если не было выведено ни одного простого числа (flag = 0), выводим сообщение “Absent”.

if flag == 0: print("Absent")